package com.ly.sort;


import org.junit.jupiter.api.Test;

import java.util.Arrays;


public class Bubbling {


    /**
     * 冒泡排序
     */
    public static void main(String[] args) {
        int[] arr = {1,2,3,5,4,6,9,7,8};

        int temp = 0;

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j]>arr[j+1]){
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }

        System.out.println(Arrays.toString(arr));
    }


    /**
     * 选择排序
     *
     * 原理 一个值与后面所有的值比较,将最小的下标记录,最后将最小值与起始下标值交换,一次按照最小排序
     *
     * 步骤:
     * 声明一个中间变量,一个记录下标
     * 外循环依次遍历
     * 内循环从外循环值的下一位开始遍历,
     * 比较外循环值与内循环值比较,大于则将内循环小标赋给记录下标,
     * 通过记录下标不断记录当前最小数,再用当前最小数继续比较,直到结束
     *  内循环结束,得到最小值下标
     *  交换最小值与外循环
     *
     */
    @Test
    public void SelectSort(){

        //定义数组
        int[] arr = {1,8,7,6,5,4,3,2,0};

        int index = 0;
        int temp = 0;

        for (int i = 0; i < arr.length-1; i++) {
            index = i;
            for (int j = i +1 ; j < arr.length; j++) {
                if (arr[index]>arr[j]){
                    index = j;
                }
            }

          //  if (index!=i){
                temp=arr[index];
                arr[index]=arr[i];
                arr[i]=temp;
          //  }
        }
        System.out.println("fdfs"+Arrays.toString(arr));
    }


    /**
     * 直接插入
     * 原理:从前往后遍历每个数,数与数组前面的所有数比较,将最小值前置到对应位置,
     *  步骤:
     * 外循依次环遍历原数组数
     * 内循环比较外循环所遍历数的前面所有数
     * 判断内循环数是否大于外循环数,
     * 大于则将外循环换成内循环的数,
     * 否则将跳出循环
     * 将初始外循环值赋给j+1
     *
     * 注意的是:内循环递减,条件>=0  i初始值为1
     *
     */
    @Test
    public void insert(){
        int[] arr = {10,8,2,6,5,4,3,1,0};
        int j = 0;
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            for (j = i-1; j >=0; j--) {
                if (arr[j]>temp){
                    arr[j+1]=arr[j];
                }else {
                    break;
                }
            }
            arr[j+1]=temp;
            System.out.println(Arrays.toString(arr));
        }
    }


    @Test
    public void String(){
        int[] arr = {10,8,2,6,5,4,3,1,0};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private void quickSort(int[] arr, int start, int end) {

        if (start<end){
            int index = getIndex(arr,start,end);
            quickSort(arr,0,index-1);
            quickSort(arr,index+1,end);
        }
    }

    private int getIndex(int[] arr, int start, int end) {
        int left = start;
        int right = end;
        int temp = arr[left];
        while (left<right){

            while (left < right && arr[right]>temp) {
                right--;
            }

            if (arr[right]<temp){
                arr[left]=arr[right];
                left++;
            }
            while (left < right && arr[right]<temp) {
                left++;
            }

            if (arr[left]>temp){
                arr[right]=arr[left];
                right--;
            }
        }
        arr[left]=temp;
        return left;
    }

    /**
     *
     * 二分法
     * 寻找指定数,
     * 当满足起始下标小于结束下标时,计算出中间位的下标,
     * 比较查找值A与数组中间值B,
     *  A>B时 结果靠近结束下标,执行起始下标++
     *  A<B时,结果靠近开始下标,执行结束下标--
     *  else 得到正确值返回此结果
     * 不满足起始下标小于结束下标时,返回null'
     */
    @Test
    public void twoPrint(){
        int[] arr = {10,8,2,6,5,4,3,1,0};
        Arrays.sort(arr);
        Integer result = find(arr,2);
        System.out.println("结果为"+result);
    }

    private Integer find(int[] arr, int temp) {

        int start = 0;
        int end = arr.length-1;
        while (start<end){
            int index = (start+end)/2;
            if (temp>arr[index]){
                start++;
            }else if (temp<arr[index]){
                end--;
            }else {
                return arr[index];
            }
        }
        return null;
    }


}
